package com.zhouyu.domain;

/**
 * @author lipengze
 * @version 1.0
 * @description: TODO
 * @date 2024/12/11 18:21
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Test {
    public ListNode partition(ListNode head, int x) {
        // 创建两个虚拟头节点
        ListNode lessHead = new ListNode(0);  // 存储小于x的节点
        ListNode greaterHead = new ListNode(0);  // 存储大于或等于x的节点

        // 当前两个链表的尾节点
        ListNode less = lessHead;
        ListNode greater = greaterHead;

        // 遍历原链表
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                // 将当前节点加入less链表
                less.next = current;
                less = less.next;
            } else {
                // 将当前节点加入greater链表
                greater.next = current;
                greater = greater.next;
            }
            current = current.next;
        }

        // 结束时，greater链表的尾部需要指向null
        greater.next = null;

        // 将less链表和greater链表连接起来
        less.next = greaterHead.next;

        // 返回重新排列后的链表的头节点
        return lessHead.next;
    }

    // 辅助函数：打印链表
    public void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    // 测试
    public static void main(String[] args) {
        Test test = new Test();

        // 示例1：6 → 5 → 4 → 3 → 2 → 1，x = 3
        ListNode head = new ListNode(6);
        head.next = new ListNode(5);
        head.next.next = new ListNode(4);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(2);
        head.next.next.next.next.next = new ListNode(1);

        System.out.println("原始链表:");
        test.printList(head);

        ListNode result = test.partition(head, 3);
        System.out.println("重新排列后的链表:");
        test.printList(result);
    }
}